Grokking Google Coding Interview
Rate this course
Ask Author
Contribute
Back to course home

0% completed

Vote For New Content
Introduction
Who Should Take This Course?
Google Easy
Add Binary (easy)
Solution: Add Binary
Valid Mountain Array (easy)
Solution: Valid Mountain Array
Set Mismatch (easy)
Solution: Set Mismatch
Is Subsequence (easy)
Solution: Is Subsequence
Length of Last Word (easy)
Solution: Length of Last Word
Search Insert Position (easy)
Solution: Search Insert Position
Repeated Substring Pattern (easy)
Solution: Repeated Substring Pattern
Monotonic Array (easy)
Solution: Monotonic Array
Count Nodes Equal to Average of Subtree (easy)
Solution: Count Nodes Equal to Average of Subtree
Find the Difference (easy)
Solution: Find the Difference
How Many Numbers Are Smaller Than the Current Number (easy)
Solution: How Many Numbers Are Smaller Than the Current Number
Binary Tree Paths (easy)
Solution: Binary Tree Paths
Find the Difference of Two Arrays (easy)
Solution: Find the Difference of Two Arrays
Merge Strings Alternately (easy)
Solution: Merge Strings Alternately
Reverse a LinkedList (easy)
Solution: Reverse a LinkedList
Google Medium
Gray Code (medium)
Solution: Gray Code
2 Keys Keyboard (medium)
Solution: 2 Keys Keyboard
Arithmetic Slices (medium)
Solution: Arithmetic Slices
Unique Length-3 Palindromic Subsequences (medium)
Solution: Unique Length-3 Palindromic Subsequences
Minimum Difference Between Largest and Smallest Value in Three Moves (medium)
Solution: Minimum Difference Between Largest and Smallest Value in Three Moves
Letter Combinations of a Phone Number (medium)
Solution: Letter Combinations of a Phone Number
01 Matrix (medium)
Solution: 01 Matrix
Maximum Points You Can Obtain from Cards (medium)
Solution: Maximum Points You Can Obtain from Cards
Strobogrammatic Number II (medium)
Solution: Strobogrammatic Number II
Maximum Length of Semi-Decreasing Subarrays (medium)
Solution: Maximum Length of Semi-Decreasing Subarrays
Minimum Area Rectangle (medium)
Solution: Minimum Area Rectangle
Count Unreachable Pairs of Nodes in an Undirected Graph (medium)
Solution: Count Unreachable Pairs of Nodes in an Undirected Graph
Single Number II (medium)
Solution: Single Number II
4Sum II (medium)
Solution: 4Sum II
Furthest Building You Can Reach (medium)
Solution: Furthest Building You Can Reach
Minimizing Array After Replacing Pairs With Their Product (medium)
Solution: Minimizing Array After Replacing Pairs With Their Product
Fair Distribution of Cookies (medium)
Solution: Fair Distribution of Cookies
Find Leaves of Binary Tree (medium)
Solution: Find Leaves of Binary Tree
Rotate Image (medium)
Solution: Rotate Image
Combination Sum (medium)
Solution: Combination Sum
Implement Trie (Prefix Tree) (medium)
Solution: Implement Trie (Prefix Tree)
Number of Islands (medium)
Solution: Number of Islands
Edit Distance (medium)
Solution: Edit Distance
Container With Most Water (Medium)
Solution: Container With Most Water
Meeting Rooms II (medium)
Solution: Meeting Rooms II
Google Hard
Shortest Subarray with Sum at Least K (hard)
Solution: Shortest Subarray with Sum at Least K
Reverse Pairs (hard)
Solution: Reverse Pairs
Nth Magical Number (hard)
Solution: Nth Magical Number
Candy (hard)
Solution: Candy
Arithmetic Slices II - Subsequence (hard)
Solution: Arithmetic Slices II - Subsequence
Burst Balloons (hard)
Solution: Burst Balloons
Sum of Distances in Tree (hard)
Solution: Sum of Distances in Tree
Maximum Score of a Good Subarray (hard)
Solution: Maximum Score of a Good Subarray
Trapping Rain Water (hard)
Solution: Trapping Rain Water
First Missing Positive (hard)
Solution: First Missing Positive
Solution: Candy

Problem Statment

You are given ratings array of integers where ratings[i] is rating value assigned to the ith child. You are giving candies to these n children who are standing in single row.

Follow below rules to give candies to each child:

  • Each child must have at least one candy.
  • Children with a higher rating get more candies than their neighbors.

Return the minimum count of candies you require to distribute candies to the children.

Examples

  • Example 1:

    • Input: ratings = [4, 2, 3, 4]
    • Expected Output: 8
    • Justification: The second child gets 1 candy (lowest rating), the third gets 2 candies (higher than the second), the first gets 2 (higher than the second but equal to the third), and the fourth gets 3 (highest rating).
  • Example 2:

    • Input: ratings = [1, 1, 1]
    • Expected Output: 3
    • Justification: All children have the same rating, so each gets 1 candy to satisfy the minimum requirement.
  • Example 3:

    • Input: ratings = [2, 4, 2, 6, 1, 7, 8]
    • Expected Output: 12
    • Justification: We can give candies to each child as given in [1, 2, 1, 2, 1, 2, 3], totaling 12 candies.

Solution

To solve this problem, we'll use a two-pass strategy to ensure fairness and efficiency. Initially, we assign one candy to every child to meet the base requirement. Then, we traverse the ratings from left to right, increasing the candy count for a child if their rating is higher than the previous child's, ensuring they receive more candies than the child before them. This guarantees that the "higher rating, more candies" rule is upheld in one direction.

However, this is not enough, as we must also check this condition in the reverse direction. To do this, we then traverse the ratings from right to left, adjusting the candy counts similarly but only increasing a child's candy if doing so would not decrease the candy count already assigned from the left-to-right pass.

This method ensures all conditions are met with the minimal amount of candy distributed, taking into account the requirements from both neighboring sides.

Step-by-Step Algorithm

  1. Initialize an Array:

    • Create an array candies with the same length as the ratings array, and fill it with 1. This ensures every child receives at least one candy initially.
  2. First Pass (Left to Right):

    • Start from the first child (index 0) and iterate through the ratings array to the last child.
    • For each child, compare their rating with the previous child's rating.
    • If the current child's rating is higher than the previous child's, increase the current child's candies by giving them one more candy than the previous child. This is done by setting candies[i] = candies[i-1] + 1.
  3. Second Pass (Right to Left):

    • Start from the last child (second-to-last index) and iterate through the ratings array towards the first child.
    • For each child, compare their rating with the next child's rating (the child on their right).
    • If the current child's rating is higher than the next child's and they do not already have more candies, adjust their candies. Specifically, give the current child one more candy than the next child if necessary, ensuring that candies[i] = candies[i+1] + 1.
  4. Calculate Total Candies:

    • Sum up all the values in the candies array. This total represents the minimum number of candies needed to satisfy the conditions.

Algorithm Walkthrough

Let's consider the Input: ratings = [2, 4, 2, 6, 1, 7, 8]

  1. Initialization:

    • ratings = [2, 4, 2, 6, 1, 7, 8]
    • candies = [1, 1, 1, 1, 1, 1, 1] (Each child gets at least one candy)
  2. First Pass (Left to Right):

    • Compare 4 to 2: Increase candies for the second child, candies = [1, 2, 1, 1, 1, 1, 1]
    • Compare 2 to 4: No increase, as 2 is not greater than 4.
    • Compare 6 to 2: Increase candies for the fourth child, candies = [1, 2, 1, 2, 1, 1, 1]
    • Compare 1 to 6: No increase, as 1 is not greater than 6.
    • Compare 7 to 1: Increase candies for the sixth child, candies = [1, 2, 1, 2, 1, 2, 1]
    • Compare 8 to 7: Increase candies for the seventh child, candies = [1, 2, 1, 2, 1, 2, 3]
  3. Second Pass (Right to Left):

    • Compare 7 to 8: No increase needed, as we're adjusting for higher ratings to the right.
    • Compare 1 to 7: No increase needed, as we're adjusting for higher ratings to the right.
    • Compare 6 to 1: No increase needed, as candies[3] > candies[4].
    • Compare 2 to 6: No increase, as we're adjusting for higher ratings to the right.
    • Compare 4 to 2: No increase needed, as the second child already has more than the third.
    • Compare 2 to 4: No increase needed, as we're adjusting for higher ratings to the right.
  4. Calculate Total Candies:

    • Summing the candies array gives us 1 + 2 + 1 + 2 + 1 + 2 + 3 = 12 candies needed in total.

Code

Java
Saved to Cloud

. . . .

Complexity Analysis

Time Complexity

  • : The algorithm involves iterating over the ratings array twice—once from left to right and once from right to left. Since each pass is linear with respect to the length of the ratings array, the overall time complexity is linear, , where n is the number of children (or the length of the ratings array).

Space Complexity

  • : Additional space is required for the candies array, which stores the number of candies for each child. This array is the same length as the ratings array, so the space complexity is .
Candy (hard)
Arithmetic Slices II - Subsequence (hard)
Mark as Completed

On this page

Problem Statment

Examples

Solution

Step-by-Step Algorithm

Algorithm Walkthrough

Code

Complexity Analysis